/**
 * The MIT License (MIT)
 *
 * Copyright (c) 2013 Armin Lunkeit, Fabian Poehland, Leonard Scharff
 *
 * Permission is hereby granted, free of charge, to any person obtaining _a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
*/

package tub.adm1;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

import tub.adm1.GoldbergTarjan.Edge;

public class Graph
{

  /**
   * map of _directed _edges
   */
  private HashMap<Integer, List<Integer>> _forward = new HashMap<Integer, List<Integer>>();

  /**
   * map of backward _edges. Only required in undirected graphs
   */
  private HashMap<Integer, List<Integer>> _backward = new HashMap<Integer, List<Integer>>();

  /**
   * Map of _vertices
   */
  private HashMap<Integer, GoldbergTarjan.Vertex> _vertices = new HashMap<Integer, GoldbergTarjan.Vertex>();
  
  /**
   * Map of _edges. The pair contains head and tail
   */
  private HashMap<Pair<Integer, Integer>, GoldbergTarjan.Edge> _edges = new HashMap<Pair<Integer, Integer>, GoldbergTarjan.Edge>();

  /**
   * Boolean flag indicating if this is _a directed graph
   */
  private boolean _directed = true;

  public Graph()
  {
    
  }
  
 
  /**
   * Initialize the graph from _a given CAT file
   * 
   * @param file
   * @throws IOException
   */
  public void init( String file ) throws IOException
  {
    String line = "";
    
    BufferedReader in = new BufferedReader( new FileReader( file ) );

    while( (line = in.readLine()) != null )
    {
      if( line.startsWith( "dir" ) )
      {
        String tokens[] = line.split( ":" );
        
        int dir = Integer.parseInt( String.valueOf( tokens[1].charAt( 0 ) ) );
        
        _directed = (dir == 0) ? false : true;
      }

      if( line.startsWith( "n" ) )
      {
        String[] s = line.split( ";" );
        GoldbergTarjan.Vertex v = new GoldbergTarjan.Vertex();
        
        for( String token : s )
        {
          String[] tokens = token.split( ":" );
          
          if( tokens[0].trim().equals( "n" ) )
          {
            v._id = Integer.parseInt( tokens[1] );
          }
          
        }
        addVertex( v );
      }

      if( line.startsWith( "h" ) )
      {
        GoldbergTarjan.Edge e = new GoldbergTarjan.Edge();
       
        String[] s = line.split( ";" );
        
        for( String token : s )
        {
          String[] tokens = token.split( ":" );
          if( tokens[0].trim().equals( "h" ) )
          {
            e._tailId = Integer.parseInt( tokens[1] );
            //e._headId = Integer.parseInt( tokens[1] );
          }
          if( tokens[0].trim().equals( "t" ) )
          {
            e._headId = Integer.parseInt( tokens[1] );
            //e._tailId = Integer.parseInt( tokens[1] );
          }
          if( tokens[0].trim().equals( "w" ) )
          {
            e._weight = Float.parseFloat( tokens[1] );
          }
        }
        
        addEdge( e );
      }
    }

    in.close();
  }
  
  /**
   * Adds _a new vertex to the graph
   * 
   * @param v
   */
  protected void addVertex( GoldbergTarjan.Vertex v )
  {
    _vertices.put( v._id, v );
    _forward.put( v._id, new LinkedList<Integer>() );
    _backward.put( v._id, new LinkedList<Integer>() );
  }

  
  public GoldbergTarjan.Vertex getVertex( int id )
  {
    return _vertices.get( id );
  }

  public GoldbergTarjan.Edge getEdge( int head, int tail )
  {
    return _edges.get( new Pair<Integer, Integer>( head, tail ) );
  }

  public boolean isEdge( int head, int tail )
  {
    return _edges.containsKey( new Pair<Integer, Integer>( head, tail ) );
  }

  protected void addEdge( GoldbergTarjan.Edge e )
  {
    _edges.put( new Pair<Integer, Integer>( e._headId, e._tailId ), e );
    _forward.get( e._headId ).add( e._tailId );
    _backward.get( e._tailId ).add( e._headId );

    /**
     * If this is an undirected graph, add _a second edge in the backward direction
     */
    if( !this._directed && !isEdge( e._tailId, e._headId ) )
    {
      Edge e2 = new Edge();
      e2._headId = e._tailId;
      e2._tailId = e._headId;
      e2._weight = e._weight;
      addEdge( e2 );
    }
  }
  
  /**
   * Returns _a list of edges from or to the vertex
   * 
   * @param id The id of the vertex
   * @return A list containing the edges
   */
  public List<GoldbergTarjan.Edge> getEdges( int id )
  {

    LinkedList<Edge> result = new LinkedList<GoldbergTarjan.Edge>();

    for( Integer neighbour : _forward.get( id ) )
    {
      result.add( getEdge( id, neighbour ) );
    }
    
    for( Integer neighbour : _backward.get( id ) )
    {
      result.add( getEdge( neighbour, id ) );
    }

    return result;
  }
  
  public List<GoldbergTarjan.Edge> deltaPlus( int id )
  {
    LinkedList<Edge> result = new LinkedList<GoldbergTarjan.Edge>();

    for( Integer neighbour : _forward.get( id ) )
    {
      result.add( getEdge( id, neighbour ) );
    }
    
    return result;
  }

  public List<Integer> deltaPlusIds( int id )
  {
    return _forward.get( id );
  }
  /**
   * Returns the vertices of the graph
   * 
   * @return
   */
  public List<GoldbergTarjan.Vertex> getVertices()
  {
    Set<Entry<Integer, GoldbergTarjan.Vertex>> set = this._vertices.entrySet();
    LinkedList<GoldbergTarjan.Vertex> list = new LinkedList<GoldbergTarjan.Vertex>();
    
    for( Entry<Integer, GoldbergTarjan.Vertex> entry : set )
    {
      list.add( entry.getValue() );
    }
    return list;
  }

  /**
   * Returns all edges of the graph
   * 
   * @return
   */
  public List<GoldbergTarjan.Edge> getEdges()
  {
    Set<Entry<Pair<Integer, Integer>, GoldbergTarjan.Edge>> set = _edges.entrySet();
    
    LinkedList<GoldbergTarjan.Edge> list = new LinkedList<GoldbergTarjan.Edge>();
    
    for( Entry<Pair<Integer, Integer>, GoldbergTarjan.Edge> entry : set )
    {
      list.add( entry.getValue() );
    }
    return list;
  }

  /**
   * Returns count of vertices
   * 
   * @return
   */
  public int vertexCnt()
  {
    return _vertices.size();
  }

  /**
   * Returns count of edges
   * 
   * @return
   */
  public int edgeCnt()
  {
    return _edges.size();
  }
  
  public boolean isDirected()
  {
    return _directed;
  }
  
  public boolean removeEdge(Integer head, Integer tail) 
  {
    try 
    {
        if (!(isEdge(head, tail))) 
        {
            return false;
        }
        this._edges.remove(new Pair<Integer, Integer>(head, tail));
        this._forward.get(head).remove(tail);
        this._backward.get(tail).remove(head);
        
        if (!(this._directed)&&isEdge(tail,head))
        {
            return removeEdge(tail, head);
        }
        return true;
    } 
    catch (Exception e) 
    {
        System.out.println("Problem when removing edge");
        return false;
    }
}

  /**
   * 
   * @author _a.lunkeit - alunkeit(at)gmail(dot)com
   *
   * @param <A> - First generic type stored in the pair implementation
   * @param <B> - Second generic type stored in the pair implementation
   */
  private class Pair<A, B>
  {
    
    A _a;
    
    B _b;

    /**
     * @param _a
     * @param _b
     */
    public Pair( A a, B b )
    {
      this._a = a;
      this._b = b;
    }

    @Override
    public int hashCode()
    {
      return _a.hashCode() + _b.hashCode();
    }
    
    @Override
    public boolean equals( Object obj )
   {
      @SuppressWarnings("unchecked")
      Pair<A, B> p = (Pair<A, B>)obj;
      
      if( null != obj )
        return this._a.equals( p._a ) && _b.equals( p._b );
      
      return false;
    }
  }
}
